package com.xyhuo.leetcode.january;

import java.util.ArrayList;
import java.util.List;

/**
 * 分割回文串
 * https://leetcode.cn/problems/palindrome-partitioning/
 *
 * @time 2024/1/12
 */
public class Partition {

//    public static void main(String[] args) {
//        Partition partition = new Partition();
//        partition.partition("aabbacca");
//    }

    public List<List<String>> partition(String s) {
        char[] charArray = s.toCharArray();
        List<List<String>>[] dp = new List[charArray.length];
        for (int i = 0; i < s.length(); i++) {
            List<List<String>> item = new ArrayList<>();
            dp[i] = item;
            for (int j = 0; j <= i; j++) {
                if (isPalindrome(charArray, j, i)) {
                    String newVal = s.substring(j, i + 1);
                    if (j - 1 >= 0) {
                        for (List<String> list : dp[j - 1]) {
                            List<String> newList = new ArrayList<>();
                            newList.addAll(list);
                            newList.add(newVal);
                            item.add(newList);
                        }
                    } else {
                        List<String> newList = new ArrayList<>();
                        newList.add(newVal);
                        item.add(newList);
                    }
                }
            }
        }
        return dp[dp.length - 1];
    }

    private boolean isPalindrome(char[] chars, int left, int right) {
        int half = (right - left) / 2;
        for (int i = 0; i <= half; i++) {
            if (chars[left + i] != chars[right - i]) {
                return false;
            }
        }
        return true;
    }
}
